#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : FreedomTrail.py
# @Time    : 2020/11/11 11:27
# @Description:
from collections import defaultdict
from functools import lru_cache


class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        """

        :param ring:
        :param key:
        :return:
        """
        lookup = defaultdict(list)
        steps = defaultdict(int)

        for i in range(len(ring)):
            tmp = ring[i:] + ring[:i]
            lookup[ring[i]].append(tmp)
            steps[tmp] = i

        def cal_steps(cur, nxt):
            tmp = abs(steps[cur] - steps[nxt])
            return min(tmp, len(ring) - tmp)

        @lru_cache(None)
        def dfs(cur, k):
            if k == len(key):
                return 0
            res = float('inf')
            for word in lookup[key[k]]:
                res = min(res, cal_steps(cur, word) + 1 + dfs(word, k + 1))
            return res

        return dfs(ring, 0)


if __name__ == '__main__':
    print('done')
